package 算法题;

/**
 * Created by Administrator on 2017/9/24.
 * 统计一个数字在排序数组中出现的次数
 */
public class KNumInArray {
    public int GetNumberOfK(int [] array , int k) {
        //排除意外情况
        int length=array.length;
        if(length==0) return 0;
        //因为是有序数组，可以确定第一个K和最后一个K出现的索引
        int firstKIndex=getFirstKIndex(array,k,0,length-1);
        int lastKIndex= getLastKIndex(array,k,0,length-1);
        //对于存在的第一和最后索引，计算次数
        if(firstKIndex!=-1&&lastKIndex!=-1) return lastKIndex-firstKIndex+1;
        //没有搜索到时
        return 0;
    }

    //二分法递归写法
    private int getLastKIndex(int[] array, int k, int start, int end) {
        //排除意外情况
        if(start>end) return -1;
        int maxIndex=array.length-1;
        int mid=(start+end)>>>1;
        if(array[mid]>k){
            return getLastKIndex(array,k,start,mid-1);
        }else if(array[mid]<k){
            return getLastKIndex(array,k,mid+1,end);
        }else if(mid+1<=maxIndex&&array[mid+1]==k){ //在array[mid]==k时，考察下一个索引是否没越界且值等于K
            return getLastKIndex(array,k,mid+1,end);
        }else { //在array[mid]==k时，下一个索引越界或者值不等于K了，那就直接返回mid索引，当做K最后一次在数组中出现的索引
            return mid;
        }
    }

    //二分法循环写法
    private int getFirstKIndex(int[] array, int k, int start, int end) {
        int mid=(start+end)>>>1;
        while(start<=end){
            if(array[mid]>k){
                end=mid-1;
            }else if (array[mid]<k){
                start=mid+1;
            }else if(mid-1>=0&&array[mid-1]==k){
                end=mid-1;
            }else{
                return mid;
            }
            mid=(start+end)>>>1;
        }
        //数组中找不到K时
        return -1;
    }
}
